module type SIGCLIENT =
sig
type landscape = string
type ready_set = string
type state = string
type move = string
val get_ready: landscape -> ready_set
val action: state -> move
end

	exception Exception of string
	let ability = ref [[1;4];[1;5];[4;5]] 
(*	let ability = ref [[1;1];[4;4];[5;5]]*)
	let friendvec = ref []
	module FM = Map.Make(struct type t = (int * int) let compare = compare end)
	let field = ref FM.empty

	let weight = 1

	(*distmax is tentative. Change if cs cannot find yh*)
(*	let distmax = ((30 + 30) * (weight + 2) )*)
	let distmax = 100

	let rec getfriendvec l n =
		match l with h::t -> if (n > 0) then (getfriendvec t (n-1)) else h
			| _ -> raise (Exception "getfriendvec with non-friend")

	let rec exist l i =
		match l with [] -> false
			| h::t -> if (h = i) then true else (exist t i)

	let car i = 
		match i with (a,b) -> a
	let cdr i = 
		match i with (a,b) -> b

	let isplainfield f =
		if ((f = 1) || (f = 5) || (f = 6) || (f = 7)) then true else false

	let parsefieldm s width =
		let rec pf s x y width e =
			let charpos = x + (y * width)
			in
			if ( x < width ) then
				(pf s (x+1) y width (FM.add (x,y) ((int_of_char (s.[charpos]))-48) e))
			else if ( charpos < String.length s ) then
				(pf s 0 (y+1) width e)
			else 
				e
		in
		(field := FM.empty);
		(field := (pf s 0 0 width (FM.empty)))
	
	let getf x y = 
		(FM.find (x,y) !field)

	let rec getability f l =
		match l with h::t -> if (f > 0) then (getability (f-1) t) else h
			| _ -> raise (Exception "getability with non-friend!")

	let shiftvec cs dir =
		if (dir = 0) then ((car cs)+1,(cdr cs))
		else if (dir = 1) then ((car cs),(cdr cs)+1)
		else if (dir = 2) then ((car cs)-1,(cdr cs))
		else ((car cs),(cdr cs)-1)

	let checknext (a,b) (c,d) =
		if ((((abs(a-c)) = 1) && (b=d))
			|| (((abs(b-d)) = 1) && (a=c))) then true else false



	let canbreak l f =
		if (f = 2) then (
			if (exist l 1) then true else false
		) else if (f = 3) then (
			if (exist l 4) then true else false
		) else if (f = 4) then (
			if (exist l 5) then true else false
		) else true
	
	let abilitystring f =
		if (f = 2) then "1"
		else if (f = 3) then "4"
		else if (f = 4) then "5"
		else "0"

	let howfar cs x y (xv,yv) fm i =
		let rec fmexist fm i =
			match fm with [] -> false
				| (h,v)::t -> if (h = i) then true else (fmexist t i)
		in

		if (fmexist fm i) then 2
		else if (checknext (x,y) (xv,yv)) then 2
		else if (((car cs)=x) && (cdr cs)=y) then 2
		else
		let rawdist = ((abs (x - xv)) + (abs (y - yv))) + 1
		in
		if (rawdist > 10) then
			(((abs (x - xv)) + (abs (y - yv))) * weight) + 1
		else rawdist

	let getclosefriend cs x y f fm =
		let rec iteratecloser x y f lv la i =
			match (lv,la) with 
				(hv::tv,ha::ta) -> (
					if (canbreak ha f) then (
						(min (howfar cs x y hv fm i) (iteratecloser x y f tv ta (i+1)))
					) else (
						(iteratecloser x y f tv ta (i+1))
					)
				)
				| _ -> 99999999
		in
		(iteratecloser x y f (!friendvec) (!ability) 0)

	let cs_past = ref []

	let getweight cs x y p d fm = (
		let f = (getf x y)
		in
		if (p = 0) then (
			((if (exist (!cs_past) (x,y)) then 1 else 0)+
			(if (isplainfield f)
				then 1 else (
					let cfd = (getclosefriend cs x y f fm)
					in
					if (cfd > d) then (cfd - d) else cfd
				)
			))

		) else (
			let fability = (getability (p-1) (!ability))
			in
			if (isplainfield f) then 1
			else if (canbreak fability f) then 2
			else 99999999
		)
	)


module type DIJK =
sig
type vec = (int * int)
type map = ((vec list) * (int * vec) list * int) FM.t
val empty: map
val finddijk: vec -> vec -> map -> (vec list) -> int -> map
val getmlist: map -> int -> int -> vec list
val getfdist: map -> int -> int -> int
val getflist: map -> int -> int -> (int * vec) list
val mapupdate: int -> int -> map -> int -> (vec list) -> (int * vec) list -> map
end

module Field : DIJK =
struct
	type vec = (int * int)
	type map = ((vec list) * (int * vec) list * int) FM.t

	let empty = (
		let rec initmap x y width e =
			if ((x > 0) && (y > 0)) then 
				(initmap (x-1) y width (FM.add ((x-1),(y-1)) ([],[],999999) e))
			else if (x = 0) then (initmap width (y-1) width e)
			else e
		in
		(initmap 30 30 30 FM.empty)
	)

	let get3 i =
		match i with (a,b,c) -> c

	let get2 i =
		match i with (a,b,c) -> b

	let get1 i =
		match i with (a,b,c) -> a

	let rec getdist m x y =
		(get3 (FM.find (x,y) m))

	let rec mapupdate x y m value l fm =
		(FM.add (x,y) (l, fm, value) m)

	let rec getmlist m x y =
		(get1 (FM.find (x,y) m))
	let rec getflist m x y =
		(get2 (FM.find (x,y) m))
	let rec getfdist m x y =
		(get3 (FM.find (x,y) m))

	let check cs nd map l p curdist fm =
		if ( (car nd) >= 30 ) then false
		else if ( (car nd) < 0 ) then false
		else if ( (cdr nd) >= 30 ) then false
		else if ( (cdr nd) < 0 ) then false
		else if (exist l nd) then false
		else (
			if (
			(curdist + (getweight cs (car nd) (cdr nd) p curdist fm)) < (getdist map (car nd) (cdr nd))
			) then true
			else false
		)

	let friendcloser cs fm curdist nd =
		let rec fmexist fm i =
			match fm with [] -> false
				| (h,v)::t -> if (h = i) then true else (fmexist t i)
		in
(*		let howfar x y (xv,yv) fm i =
			if (fmexist fm i) then 2
			else 
				(((abs (x - xv)) + (abs (y - yv))) * weight)
		in*)
		let rec iteratecloser x y f lv la i =
			match (lv,la) with 
				(hv::tv,ha::ta) -> (
					let closest = (iteratecloser x y f tv ta (i+1))
					in
					if (canbreak ha f) then (
						let distt = (howfar cs x y hv fm i)
						in
							let distt =
							if (distt > curdist) then (distt - curdist)
							else distt
						in
						if (distt < (cdr closest)) then (
							(i, distt)
						) else (
							closest
						)
					) else (
						closest
					)
				)
				| _ -> (2, 99999999)
		in
		let f = (getf (car nd) (cdr nd))
		in
		if (isplainfield f) then fm
		else
			((car (iteratecloser (car nd) (cdr nd) f (!friendvec) (!ability) 0)), nd)::fm(*!!*)

	let finddijk o_cs yh map l p = (
	(* p: who is moving? 0 is cs, else is friend *)

		let rec dijk cs yh map l p fm =
			let nextdijk_A cs ns yh map l p fm curdist = 
				if (check cs ns map l p curdist fm) then
					(dijk ns yh 
						(mapupdate (car ns) (cdr ns) map 
						(curdist + (getweight o_cs (car ns) (cdr ns) p curdist fm))
						(cs::l)
						fm
						)
					(cs::l) p (friendcloser cs fm curdist ns))
				else (map)
			in
			let curbest = (getdist map (car yh) (cdr yh))
			in
			let curdist = (getdist map (car cs) (cdr cs))
			in
			let nextdijk dir map =
				(nextdijk_A cs (shiftvec cs dir) yh map l p fm curdist)
			in
			if (curdist >= curbest) then map
			else if (curdist >= distmax) then map
			else(
				if ((car cs) < (car yh)) then (
					let map = (nextdijk 0 map) in
					let map =
					if ((cdr cs) < (cdr yh)) then (
						let map = (nextdijk 1 map) in
						let map = (nextdijk 3 map) in
						map
					) else (
						let map = (nextdijk 3 map) in
						let map = (nextdijk 1 map) in
						map
					) in
					let map = (nextdijk 2 map) in
					map
				) else (
					let map = (nextdijk 2 map) in
					let map =
					if ((cdr cs) < (cdr yh)) then (
						let map = (nextdijk 1 map) in
						let map = (nextdijk 3 map) in
						map
					) else (
						let map = (nextdijk 3 map) in
						let map = (nextdijk 1 map) in
						map
					) in
					let map = (nextdijk 0 map) in
					map
				)
			)
		in
		 dijk o_cs yh map l p []
	)
end

let getstr i =
	if i > 9 then (string_of_int i) else "0"^(string_of_int i)

let abs i = if ( i < 0 ) then (-i) else i

let rec printveclist l =
	match l with [] -> (print_string "--\n")
		| (a,b)::t -> (print_int a);(print_string ", ");(print_int b);
		(print_string "\n");(printveclist t)

let rec printflist l =
	match l with [] -> (print_string "--\n")
		| (a,(q,w))::t -> (print_int a);(print_string " (");
			(print_int q);
			(print_string ",");
			(print_int w);
			(print_string ")\n");(printflist t)


module Client : SIGCLIENT =
struct
	type landscape = string
	type ready_set = string
	type state = string
	type move = string

	let parse_xy str offset =
		(
		((int_of_string (String.sub str offset 2))
		,
		(int_of_string (String.sub str (offset+2) 2))
		)
		)
	
	let rec parse_friend str offset count =
		if ( count > 0 ) then (
			(friendvec := (!friendvec)@[(parse_xy str offset)]);(parse_friend str (offset+4) (count-1))
		) else (
			()
		)
	let makevecstring v =
		(getstr (car v))^(getstr (cdr v))

	let makeaction cs_o cs p =
		let cs = if (checknext cs cs_o) then cs else cs_o
		(*This should not be necessary!!*)
		in
		let csf = (getf (car cs) (cdr cs))
		in
		if (p = 0) then (
			if (isplainfield csf) then
				((cs_past := (cs::(!cs_past)));(makevecstring cs))
			else 
				(makevecstring cs_o)

		) else (
			let fability = (getability (p-1) (!ability))
			in
			if (isplainfield csf) then
				"0"^(makevecstring cs)
			else if (canbreak fability csf) then
				(abilitystring csf)^(makevecstring cs) (*!!*)
			else "0"^(makevecstring cs_o)

		)

	let get_ready l  =
		(cs_past := []);(
(*		"I1408131508144508150812"*)
		"I1402021502204502270213"

		)

	let makefstrings fm cs cs_next =
		let rec getfdest fm i o =
			match fm with [] -> o
				| (a,b)::t -> if (a = i) then b else (getfdest t i o)
		in
		let rec iteratef fl i =
			let fr = (getfriendvec fl i)
			in
			let yh = (getfdest fm i fr)
			in
			if (cs = fr) then (makeaction fr cs_next (i+1)) 
			else if (checknext fr cs) then (makeaction fr cs (i+1))
			else if (yh = fr) then (makeaction fr fr (i+1))
			else if (checknext fr yh) then (makeaction fr yh (i+1))
			else
				let f_dijk = (Field.finddijk fr yh 
					(Field.mapupdate (car fr) (cdr fr) Field.empty 0 [] [])
					[] (i+1))
				in
				let f_ll = (List.rev (Field.getmlist f_dijk (car yh) (cdr yh)))
				in
				match (f_ll) with h::n::t -> 
						(makeaction fr n (i+1))
					| h::t -> (makeaction fr h (i+1))
					| _ -> (makeaction fr fr (i+1))

		in
		(iteratef (!friendvec) 0)^(iteratef (!friendvec) 1)^(iteratef (!friendvec) 2)

	let step = ref 0

	let action l =
	(

	(parsefieldm (String.sub l 1 (30 * 30)) 30); (* 5 : 'I' + YH pos*)
	
	let cs = (parse_xy l ((30*30)+13))
	in
(*	let yfriend = (parse_friend l ((30*30)+17) 3)
	in*) (*We don't use opponent data yet*)
(*	let ys = (parse_xy l ((30*30)+29))
	in*)
	let yh = (parse_xy l ((30*30)+33))
	in
	(step := (!step) + 1);
	(*(print_int !step);
	(print_string ( "  "^(makevecstring cs)^"\n"));*)
	(friendvec := []);(parse_friend l ((30*30)+1) 3);(
		let dijk = (Field.finddijk cs yh 
			(Field.mapupdate (car cs) (cdr cs) Field.empty 0 [] []) 
			[] 0)
		in
		let ll = (List.rev (Field.getmlist dijk (car yh) (cdr yh)))
		in
		let fl = (List.rev (Field.getflist dijk (car yh) (cdr yh)))
		in
		(*printflist fl);*)
		(*(printveclist ll);*)
		let cs_next = 
			if (checknext cs yh) then yh
			else (
				match (ll) with h::n::t -> 
					n
					| h::t -> h
					| _ -> cs
				)
			
		in
		let cs_s = (
			if (checknext cs yh) then (makeaction cs yh 0)
			else (
				match (ll) with h::n::t -> 
					(makeaction cs n 0)
					| h::t -> (makeaction cs h 0)
					| _ -> (makeaction cs cs 0)
				)
			)
		in
		let frs = (makefstrings fl cs cs_next)
		in
		let finalstring = "M"^frs^cs_s
		in
		(print_int (Field.getfdist dijk (car yh) (cdr yh)));
		(print_string "\n");
		(*(print_int (String.length finalstring));
		(print_string finalstring);
		(print_string "\n");*)
		finalstring
		)
	)
end
